Two apparatus that take part in a key exchange system communicate with each other to share one key. A system wherein each apparatus has a process of authenticating itself and authenticates a companion apparatus with which the apparatus has exchanged a key is called an authentication and key exchange system. If communications performed between the two apparatus to exchange keys do not certify that the apparatus have communicated with each other, then the system is called a deniable authentication and key exchange system.
One example of relevant deniable authentication and key exchange system is disclosed in the document: Mario Di Raimondo, Rosario Gennaro, and Hugo Krawczyk, “Deniable Authentication and Key Exchange”, 13th ACM Conference on Computer and Communication Security. A summary of the relevant deniable authentication and key exchange system will be described below.
FIG. 1 is a diagram illustrative of the relevant deniable authentication and key exchange system.
As shown in FIG. 1, two key exchange apparatus A.107, B.108 for exchanging keys are communicably connected to each other. Key exchange apparatus A.107 will hereinafter be simply referred to as “apparatus A” and key exchange apparatus B.108 as “apparatus B”.
Apparatus A is supplied with private key 101 of its own, public key 103 of apparatus B, and random number 113. Apparatus B is supplied with private key 104 of its own, public key 102 of device A, and random number 114. It is assumed that private key 101 is denoted by skA, private key 104 by skB, public key 102 by pkA, and public key 103 by pkB, and also that random number 113 is denoted by rA and random number 114 by rB.
Each of apparatus A, B incorporates therein an encrypting device and a decrypting device according to the public-key cryptography. The keys such as pkA, skA, etc. are public keys and private keys that are used according to the public-key cryptography with which apparatus A, B are compatible. Each of the apparatus additionally incorporates an authenticating device and a pseudo-random number generator.
It is assumed that p represents a prime number and g a generating element of a subgroup of prime number order q of (Z/pZ)*. These p, q are sufficiently large. Initially, apparatus A starts communications. This will not lose generality.
An operating sequence of apparatus A and apparatus B will briefly be described below.
Apparatus A randomly selects x ε Z/qZ and key kA of the authenticating device. Apparatus A then generates hA=gx and cryptotext cA based on pkB of kA, and sends them to apparatus B (as indicated by reference numeral 115 in FIG. 1).
Apparatus B randomly selects y ε Z/qZ and key kB of the authenticating device. Apparatus B then generates hB=gy and cryptotext cB based on pkA of kB. When apparatus B receives hA=gx and cA from apparatus A, apparatus B decrypts cA using skB. The decrypted result is represented by kA′. Then, apparatus B generates authentication code tB for hA, hB using kA′. Thereafter, apparatus B sends hB, cB, and tB to apparatus A (as indicated by reference numeral 116 in FIG. 1).
When apparatus A receives hb, cB, and tB from apparatus B, apparatus A verifies authentication code tB for hA, hB using kA. If the authenticated result is not correct, then the sequence stops. If the authenticated result is correct, then apparatus A decrypts cB using skA. The decrypted result is represented by kB′.
Then, apparatus A generates authentication code tA for hA, hB using kB′. Apparatus A generates pseudo-random number qA from hBx with the pseudo-random number generator, using kA as a key, and also generates pseudo-random number qB′ from hBx with the pseudo-random number generator, using kB′ as a key. Apparatus A then outputs exchanged key 110 as the result of an exclusive OR on qA and qB′ per bit. Finally, apparatus A sends tA to apparatus B (as indicated by reference numeral 117 in FIG. 1).
When apparatus B receives tA from apparatus A, apparatus B verifies authentication code tA for hA, hB using kB. If the authenticated result is not correct, then the sequence stops.
If the authenticated result is correct, then apparatus B generates pseudo-random number qA′ from hAy with the pseudo-random number generator, using kA′ as a key, and also generates pseudo-random number qB from hAy with the pseudo-random number generator, using kB as a key. Finally, apparatus B outputs exchanged key 111 as the result of an exclusive OR on qA′ and qB per bit.
Apparatus A possibly outputs a knowledge obtained as a result of the communication with apparatus B as history 109. Apparatus B possibly outputs a knowledge obtained as a result of the communication with apparatus A as history 112.